For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
0answers
25 views

To find the best success list among players?

In a Sport league, There are teams or players and their match results are known with each other. How can we do a fair list for players that shows their success in? I would like to give an example to ...
3
votes
0answers
14 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
7
votes
0answers
105 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
1
vote
1answer
25 views

How is Schroeder's generalized parentheses sequence (A001003) actually used to generated parentheses expressions?

The sequence A001003 counts the "number of ways to insert parentheses in a string of n+1 symbols". What I'm trying to figure out is how to generate the expressions with parentheses (in code). For ...
0
votes
1answer
48 views

variation to tower of hanoi problem

Here is the question: There are $m$ different sizes of disks and exactly $n_k$ disks of size $k$. Determine $A(n_l,. . . , n_m)$, the minimum number of moves needed to transfer a tower when ...
7
votes
2answers
216 views

Sum of 1.5-powers of natural numbers

I recently have met the following approximate equation: $$\sum_{k=1}^n k^{1.5}\approx\frac{n^{2.5}+(n+1)^{2.5}}{5}.$$ It's a rather accurate approximation (for $n=40$ the absolute error is $\approx ...
1
vote
2answers
22 views

Word problem on collecting specified liters with two pails

I am thinking through an interesting puzzle. John is near a lake and has two pails, one holding 4 liters, the other holding 7 liters. The pails have no markings. All John knows is if a pail is empty ...
1
vote
4answers
303 views

What a good approach will be to solve this problem?

I know that this function from A to A is 1-1 and also onto. How many functions like this exists ? The set A contain 12 elements. $$\forall a \in A $$ $$f(f(a)) \ne a{\rm{ , }}$$ $$f(f(f(a))) = ...
-1
votes
1answer
36 views

Given a sequence of n numbers how to count all contiguous subsequences containing a particular number.

Let a given sequence be - $1, 5, 2, 4$ then the total number of contiguous subsequences containing the number $5$ are the following six sequences: $1, 5, 2, 4$ $1, 5, 2$ $5, 2, 4$ $1, 5$ $5, 2$ ...
0
votes
1answer
96 views

Finding number of subarrays not including certain pairs

How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array? For eg. if array ={11,22,33,45} and if we do not want to include say position ...
-1
votes
2answers
32 views

How many ways to arrange colors (constraints)

Ed has five identical green marbles and a large supply of identical red marbles. He arranges the green marbles and some of the red marbles in a row and finds that the number of marbles whose right ...
-5
votes
1answer
32 views

combinations of 5 groups question [duplicate]

I have $25$ people who will be split in to groups of $5$ people each day over $5$ days in $5$ different locations. Can I rotate them so they all meet each other only once and visit each location once ...
2
votes
1answer
38 views

A Permutations/Combinations Question and Inquiry on Good Source for Studying The Concept

Lets say a burger joint offers options for customizing burgers. There are 3 types of meats and 7 condiments. A burger must include meat but may include as many or as few condiments as the customer ...
2
votes
4answers
67 views

Number of Interesting Quadruples

Define an ordered quadruple of integers $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$, and a+d>b+c. How many interesting ordered quadruples are there? This is a bit of trouble ...
0
votes
0answers
19 views

choosing Minium Set from N numbers [duplicate]

I have to make a set by using number in between 1 to N number such that two consecutive set have no number in common and lexicographically sorted and also if we choose any integer from 1 to N then ...
2
votes
0answers
55 views

How many anagrams of a given word exists with constraints

I saw many questions about anagrams here, but neither one fits my needs. Let's say we have the word MISSISSIPPI. I need to find the count for those anagrams that meet the criterias as follows: ...
0
votes
1answer
31 views

Using generating functions to solve a distribution of distinct objects.

How many ways can $r$ distinct objects be distributed into $4$ distinct containers if there must be at most $1$ object in the first container? I think I have done this problem correctly. Can ...
4
votes
1answer
75 views

How many words can be made with $7$ A's, $6$ B's, $5$ C's and $4$ D's with no consecutive equal letters.

I would like to know how many $22$ letter words can be made that have exactly $7$ A's, $6$ B's , $5$ C's and $4$ D's and have no consecutive letters the same. This problem is clearly equivalent to ...
0
votes
2answers
44 views

A three-character password, how many different passwords are possible?

a three-character password consists of 2 different digits between 0 and 9 inclusive. and 1 letter of the English alphabet. the letter must appear as first or second character, how many different ...
0
votes
1answer
21 views

How many paths touch each node a given number of times?

How many paths of length $N$ through a complete graph pass a given number of times $k_n$ through each node $n$ ($\sum_n k_n = N$)?
0
votes
2answers
21 views

What kind of permutation/combination is this?

I have 2 letters to choose from, and 3 positions I can place them in, where order matters. Lets say letters A and B: The possibilities, from an intuitive sense are: AAA, BAA, BBA, BAB, ABB, BBB, ...
0
votes
0answers
26 views

Maximum size of a union of incomparable chains

Let $\mathbb{N}^{<\mathbb{N}}$ denote the set of finite sequences of natural numbers (not including the empty sequence). Order this set by $E\preceq F$ if $E$ is an initial segment of $F$. Call a ...
1
vote
0answers
27 views

Is the Library of Babel random? Does it contain information?

The Library of Babel is defined as a universe in the form of a vast library containing all possible 410-page books of a certain format and character set. However, applying two means of ...
0
votes
2answers
83 views

How many permutations of the letters AEIOU contain the strings EA and UO?

So here is our "word" AEIOU. Then we need to find how many permutations contain EA and UO. Then how many contain AE and EI and how many end with O. I know how to figure out some of these problems ...
1
vote
0answers
18 views

determinant of independent set of triangles

let $n > 3$. To a square free trinomial $x_i x_j x_k$ associate the $n$ vector that has all entries zeros except in the $i$-th, $j$-th, and $k$-th entries, where it has the value $1$ (i.e. all ...
7
votes
1answer
62 views

The distance between the origin and all intersections by the diagonals of a regular polygon

The geometric center of an n-sided regular polygon is point $O$. Connect all diagonals of the polygon. How many different distances between diagonal-diagonal intersections ($O$ itself is counted) and ...
-1
votes
1answer
45 views

Counting number of subarrays that satisifies the given property.

Given an array A having n elements and a number K,I want to count the number of subarrays(i.e Elements need to be contiguous) of A, such that no 2 elements in the subarray holds the property ...
0
votes
1answer
24 views

Linear/Integer programming reference request

There are a few other similar questions out there, but I think mine is not a duplicate because I am looking for a different kind of references than most people. I am primarily a discrete ...
0
votes
0answers
35 views

Number of ways to color a row of objects with a fixed number of boundaries

Number of ways to color a row of $N$ objects with $M$ colors ($M<N$) so that there are $N_i$ objects of each color $i$ ($i=1, ... , M$ ) and $k$ boundaries. The values $\{N_i\}_i$ are fixed, and so ...
3
votes
3answers
124 views

How many functions $f: A\rightarrow A$ exist without (?) any $f(x)=x$

The definition: $\mathcal A = \{1\cdots12\}$ $\mathcal f: A \rightarrow A$ for each $\mathcal x \in A$, $\mathcal f$ is defined $\mathcal f(f(x)) \neq x$ and $\mathcal f(f(f(x))) = x$ How many ...
1
vote
2answers
50 views

How many different groups of $4$ can be made from $142$?

I performed this weekend in what we call extreme quarteting. We had $142$ people and we wanted to know how many different groups of $4$ can $142$ people make?
1
vote
3answers
144 views

A set of cards from which I can identify and number $n$ with $1\le n\le N$

I am working with a collection of cards. On each card is written a set of numbers $1\le n\le N$ in ascending order. When I arrange the cards in lexicographic order on the table, no two adjacent cards ...
0
votes
1answer
58 views

combinations groups question

I have 25 people who will be split in to groups of 5 people each day over 5 days. Can I rotate them so they all meet each other only once? Help! Sorry forgot to mention they all meet in 5 different ...
2
votes
1answer
43 views

Number of edges in the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,…,n\}$

I am stucked at this problem: Let $G$ be the graph defined as the the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,...,n\}$. ($n>0$) Determine how many edges ...
0
votes
1answer
48 views

Number of ways of putting a set of N objects into 5 boxes (2 Blue, 1 Red, 1 Green and 1 Yellow)

Problem: Let's say we have set of "N = 12" objects of which 3 are identical footballs, 4 are identical tennis balls and 5 are identical golf balls. Let's say we have 5 buckets, of which two are Blue, ...
1
vote
2answers
40 views

Finite sums of integers and similar problems: book request

I recently learned about Faulhaber's formula, which says that for each integer $p \geq 1,$ we can simplify the finite sum $\sum_{k \in \mathbb{N}}[k<n]k^p$ so that it becomes an (integer-valued) ...
0
votes
2answers
49 views

Distinguishable Objects in a Circular Arrangement

I asked a question, AOPS Math Jam If you look at #9: **Please CTRL:F -> ** this: *"Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least ...
2
votes
2answers
87 views

A combinatorial identity No. 2

I have no idea how to simplify ( if possible at all ) this sum $$\sum_{k=0}^{n}(-1)^k\binom{x}{n-k}\binom{y-2x}{k}2^k$$ It would be fine if a 1-binomial expression formula would result.
0
votes
1answer
30 views

Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items. The algorithm works using the recursive formula of the binomial coefficient ...
2
votes
1answer
66 views

How is this equation evaluated $\binom {n}2 = \frac{n^2}{2}$?

I would like to know how $\binom {n}2 = \dfrac{n^2}{2}$ works out while I'm reading a proof on this page. I have tried several ways, but I couldn't. i.e. we knew that combinatorics formula that ...
1
vote
0answers
37 views

Composing a permutation with a transposition and length

Let $\pi$ be an element of the permutation group $S_n$, such that, when it operates on the ordered set $\{1, 2, \ldots , N\}$, the ordered set that it produces $\{k_1, k_2, \ldots , k_N\}$ has two ...
-1
votes
0answers
48 views

In a generalized birthday problem, how is this simplification done?

I am trying to understand generalization of birthday paradox in probability as it is explained here. I think I got the whole solution except the below simplification. ...
1
vote
2answers
61 views

How to find an exponential generating function if we know a usual generating function? [duplicate]

Suppose we know a usual generating function of a sequence $a_0,a_1, a_2 \ldots :$ $$ f(x)=a_0+a_1 x+a_2 x^2+\cdots, $$ Question. It is possible to find an exponential generating function for the ...
5
votes
2answers
49 views

Card Draw question

What are the ways to draw 13 cards from a pack of 52 cards such that (a) the hand is void in at least one suit, (b) the hand is not void in any suit.(“void in a suit” means having no cards of that ...
1
vote
0answers
73 views

combinatorics problem about counting

Suppose a $n$-sided regular that labeled every vertex from $1$ to $n$. We know can draw $\frac {(n)(n-3)}{2}$ diameter in $n$-sided regular. We also know if we want to draw the diameters that none ...
2
votes
0answers
27 views

how to prove this graph problem?

to every point $X$ in the plane is assigned a real number $r(x) > 0$ such that for any two points $X$ and $Y$ in the plane $2|r(x)-r(y)|<|XY|$ where $|XY|$ is the linear distance between the two ...
0
votes
2answers
104 views

Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
3
votes
3answers
60 views

Solve the following simple congruence

$$560x \equiv 1 \pmod{429}$$ I am close, I used Euclid's algorithm but the remainder is hard to go backwards. $$560 = 1(429) + 131 $$ $$429 = 3(131) + 36$$ $$131 = 3(36) + 23$$ $$36 = ...
3
votes
4answers
241 views

Integer solutions using PIE

Find the number of integer solutions to $a+b+c+d=18$ with $ 0≤a,b,c,d≤6$. With no restrictions there are: $$\binom{21}{3} = 1330$$ Ones that are invalid are: $a, b, c, d \ge 7$. But how do I ...
0
votes
1answer
47 views

Find the number of polynomials satisfying the root conditions

Let $S$ be the set of all polynomials of the form $z^3+az^2+bz+c$, where $a$, $b$, and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either ...