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)

3
votes
1answer
108 views

What do you call a set whose subsets all have unique sums?

An example would be $\{1, 3, 7\}$, which has subsets with sums $1, 3, 7, 4, 10, 8, 11$. What is this called?
48
votes
14answers
10k views

Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?

I'm not a very smart man. I'm trying to count how many years I've been working at my new job. I started in May 2011. If I count the years separately, I get that I've worked 4 years - 2011 (year 1), ...
3
votes
1answer
37 views

Number of distinct grids formed

Let $n$ be a positive integer and let $\mathcal{G}_n$ be an $n\times n $ grid with the number $1$ written in each of its squares. In each step we multiply all entries of a row or column is multiplied ...
0
votes
1answer
101 views

To calculate number of combination of sequences having 1 and 2 alternating sequences of R and S.

I have a sequence of 6 letters containing two P, two R, one Q, and one S. I have PPQ. Now I have to add two R and one S in that; these can be placed anywhere. There will be in total $60$ possible ...
1
vote
1answer
38 views

Extracting the coefficient of $x^n$ from a fraction

I need help extracting the coefficient of $x^n$ from a $\frac{1-x}{1-2x}$. So far I have that \begin{align} \frac{1-x}{1-2x} &= \frac{1}{1-2x} - x\frac{1}{1-2x}\\ &= \sum\limits_{k=0}(2x)^k ...
1
vote
1answer
47 views

Upper bound of $\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$

I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found $S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$ but It seems it's ...
2
votes
2answers
2k views

Lexicographical rank of a string with duplicate characters

Given a string, you can find the lexicographic rank of the string using this algorithm: Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 ...
0
votes
1answer
299 views

Number of triangles formed by all chords between $n$ points on a circle

We have $n$ point on circumference of a circle. We draw all chords between this points. No three chords are concurrent. How many triangles exist that their apexes could be on circumference of ...
0
votes
1answer
47 views

Distribution, Combination,Arrangments

How many ways can $25$ distinguishable balls be placed in two distinguishable boxes? Order/placing doesn't matter. Only unique combinations accepted (e.g., a blue ball whether placed in a box first ...
-2
votes
1answer
29 views

Distribution combinations [closed]

How many ways can $25$ identical pencils be distributed between two people? Each pencil must be given out. a) Each person must have at least $5$ pencils. b) Each person must have at least $7$ ...
4
votes
1answer
99 views

What is this sequence of all permutations with gaps permissible [duplicate]

Let there be a sequence $a_1, a_2, a_3,...,a_n$ that represent some actions that you know are required to solve a problem. However, you do not know what order these actions need to be taken to solve ...
0
votes
3answers
87 views

How many four digit numbers begin with $10$?

How many combinations are there for a four digit combination that starts with ten. I have a safe that requires four numbers and I know that the first two numbers are one and zero. I do not remember ...
1
vote
1answer
199 views

Is there a set of 69 length-6-sets out of 46 numbers [1..46] so that those length-6-sets “cover” all possible 1035 length-2-sets of 46 numbers?

1.) For this question, we have 46 numbers (balls, cards, whatever): {1,2,3,4 .... 45,46} ======================= 2.) Each length-6-set of 46 numbers ( e.g. {1,2,3,4,5,6} or {1,13,16,17,32,46 } '...
1
vote
0answers
36 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
2
votes
1answer
61 views

A small variation of the Magic square problem

Let us consider a $n \times n$ grid squares. We put numbers from $0$ to $n^{2}$ ( note that you can omit any one number from $0$ to $n^{2}$ ) such that sum of elements in each row ,each column and ...
1
vote
1answer
50 views

paths from from point A to point B with length 8

Question How many paths from point A to point B with length 8 exists that that have even number of negative signs? path example my main problem is that i can't find a good way for counting paths....
0
votes
1answer
46 views

prove $a^2_o-a^2_1+a^2_2-…+(-1)^{n-1}a^2_{n-1}=\frac {1}{2}(a_n+(-1)^{n+1}a^2_n)$

Question if $a_k$ is multinomial coefficient of $x^k$ in polynomial $(1+x+x^2)^n$,where $0\le k\le 2n$,prove: using this equality $(1+x+x^2)(1-x+x^2)=1+x^2+x^4$,show that $$a^2_o-a^2_1+a^2_2-...+(-...
2
votes
0answers
54 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers $\{a_1,\dots,a_n\}$ and another number $k$. I need to find whether sum of any combination of numbers in the set produces $k$. It can be $a_1 + a_2$ or $a_1 + a_2 + a_3 + a_7$. ...
1
vote
0answers
43 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
2
votes
2answers
118 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
100 views

Proof that ordinary multinomial coefficients rise monotonically to a maximum and then decrease monotonically

While most computations of ordinary multinomial coefficients for the following case require recursive summations, I found here a closed-form solution: $$(1+x+x^2+\cdots+x^q)^L = \sum_{a \geq 0} \...
1
vote
1answer
67 views

Will I will be able to sit and watch the movie?

Recently I went to the theater. When I came to buy my $3$ tickets (two friends and I), the machine tells me that there is $18$ seats out of $300$ ($15$ rows of $20$ seats). What is the probability ...
1
vote
1answer
56 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
2
votes
1answer
32 views

What are the probability that the first two rows of the class are full?

I was boring in my class. So I ask myself the question: What are the probability that the first two rows of the class are full? Knowing that we're $25$ students in my class and the class have $...
6
votes
0answers
146 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
5
votes
3answers
146 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
1
vote
0answers
46 views

The probability that exactly / at-least $k$ numbers are in the correct position [duplicate]

Given a sequence of $[1,\dots,n]$ in random order: Let $P_k$ be the probability that exactly $k$ numbers are in the correct position Let $Q_k$ be the probability that at least $k$ numbers are in the ...
1
vote
1answer
211 views

solving by stars and bars methods

In how many different orders can the people Alice, Benjamin, Charlene, David, Elaine, Frederick, Gale, and Harold be standing on line if each of Alice, Benjamin, Charlene must be on the line before ...
0
votes
1answer
456 views

About permutation with repeated identical elements.

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this: ...
2
votes
0answers
90 views

A combinatorics problem about $n\times n$ square

In a $n\times n$ square, a coordinate arrangement is defined as $n$ cells such that for any row or column, there is only one cell taken. For instance, the arrangement taking the diagonal line is ...
4
votes
1answer
71 views

Simple counting problem

Suppose that you have a box with $n$ balls, from the $n$ balls $k$ are white and $n-k$ are black. Now, sequentially you draw (without replacement) the $n$ balls in groups of $m$ (a natural number that ...
6
votes
1answer
145 views

Can the product of $n$ factorials be $n$ factorial?

Are there any solutions to the equation $a_1!\cdot a_2!\cdots a_n!=n!$ with all variables being integers greater than or equal to $2$?
3
votes
2answers
60 views

Proof $e^n*n!$ is an asymptote of $(n+1)^n$

I would like to prove $\lim_{n\to \infty}e^nn!-(n+1)^n=0$. All I have really done is show $(n+1)^n=\sum_{i=0}^n\frac{n!}{(n+1)^i(i!)(n-i)!}$
4
votes
2answers
311 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
1
vote
1answer
140 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers $k,n$...
4
votes
1answer
131 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as $\...
0
votes
4answers
2k views

how many words can be formed using all letters in the word EXAMINATION

Assuming any sequence of letters is a word, how many words can we form in such a way that the first two letters are different consonants while the last two letters are vowels?
0
votes
2answers
67 views

What is the minimum number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the minimum number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My ...
1
vote
1answer
108 views

Number of $n$ letter words from letters a,b that contain exactly $m$ substrings “ab”

I want to prove the number of $n$ letter words that just have letters a,b that exactly have $m$ "ab" expression is $n+1 \choose ...
0
votes
1answer
1k views

Combination with repition, Representation techniques.

Consider the following Question:A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernick bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are ...
3
votes
2answers
151 views

number of ways to put 4 black,4 white,4 red balls in 6 different boxes

The question says:in how many ways we could put 4 black,4 white,4 red balls in 6 different boxes? boxes are distinguishable,black balls are identical,red balls are identical,and white balls are ...
0
votes
0answers
95 views

Question about Combinatorics [duplicate]

I understand that for a problem such as 59C5 there are 5,006,386 possible combinations. Is there a way mathematically to determine exactly how many of the 5,006,386 5-digit combinations will sum to a ...
-1
votes
3answers
2k views

How can I calculate the total number of possible anagrams for a set of letters?

How can I calculate the total number of possible anagrams for a set of letters? For example: "Math" : 24 possible combinations. ...
1
vote
0answers
42 views

Rotation Algorithim

I have a series of 7 tables and 73 participants in a roundtable discussion. My challenge is to rotate all 73 participants to each of the 7 tables while minimizing the times in which they sit with the ...
2
votes
1answer
85 views

Total number of unique n-element sets from a base of unique elements

I have searched for the answer for this on the site (and on the Internet) and have not found the answer. I do apologize if this is answered and I do not have the vocabulary to ask or search for the ...
2
votes
1answer
47 views

Subjectivity in combinatorics

I found some questions in combinatorics very subjective for example: With the digits $1,2,3,4,5,6$, how many 4-uplas exists (order matters) where the digit 1 is before 4? The solution of this ...
3
votes
1answer
80 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
10
votes
1answer
208 views

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that $e(G[V_i]...
4
votes
2answers
94 views

A game with checkers

Alice puts checkers in some cells of a $8 \times 8$ board such that : There is at least one checker in any $1\times 2$ or $2\times 1$ rectangle. There are at least two adjacent checkers in any $7\...
0
votes
2answers
34 views

How to find a pointset with unique distances

Is there a way to arrange N number of 2D points within a box so that the distances between the points are unique? I have an application where I can measure the distances between points with some ...